package pers.qianyu.month_202102.date_20210216;

/**
 * 72. 编辑距离
 * https://leetcode-cn.com/problems/edit-distance/
 * - 状态压缩
 *
 * @author mizzle rain
 * @date 2021年2月16日21:53:10
 */
public class MinDistance2 {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        if (m == 0) return n;
        if (n == 0) return m;
        char[] arr1 = word1.toCharArray();
        char[] arr2 = word2.toCharArray();
        int[] dp = new int[n + 1];
        for (int i = 0; i <= n; i++) dp[i] = i;
        for (int i = 1; i <= m; i++) {
            int pre = i - 1;
            dp[0] = i;
            for (int j = 1; j <= n; j++) {
                int t = dp[j];
                if (arr1[i - 1] == arr2[j - 1]) dp[j] = pre;
                else dp[j] = Math.min(dp[j], Math.min(dp[j - 1], pre)) + 1;
                pre = t;
            }
        }
        return dp[n];
    }
}